<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>Title</title>
</head>
<body>
<p>
  时间复杂度与空间复杂度
  1. 时间复杂度： 基数排序的时间复杂度为O(nk)，其中n为数据量，k为元素的最大位数。这是因为基数排序需要进行k趟排序，每趟的时间复杂度为O(n)。
  2. 空间复杂度： 基数排序需要额外空间存储桶，空间复杂度为O(n + k)。其中，n为数据量，k为基数（如10进制下的10个桶）。
</p>
<p>
  特点：
  1. 非比较型排序：基数排序不依赖元素间的比较操作，而是利用元素的位值进行排序。
  2. 稳定：由于元素是按照其位值放入对应的桶中，且桶内元素顺序不变，因此基数排序是稳定的排序算法。
</p>
<p>
  优点：
  1. 高效：对于整数或具有整数编码的字符串等数据，基数排序具有线性时间复杂度，效率极高。
  2. 稳定：保持相等元素的原始相对顺序，适用于需要稳定排序的场景。
  3. 适合海量数据：由于其线性时间复杂度和相对较低的空间复杂度，基数排序在处理大规模数据时表现出色。

  缺点：
  1. 数据类型限制：基数排序适用于整数或可以转化为整数编码的字符串等数据，对于浮点数、复杂对象等数据类型，需要进行适当的预处理才能应用。
  2. 空间消耗：需要额外空间存储桶，对于极其受限的内存环境，可能需要权衡空间与时间的效率。
</p>
<p>
  应用场景
  1. 大规模整数排序 当待排序数据为大量整数或整数编码的字符串时，基数排序能充分利用数据特性，实现高效排序。例如，电话号码、身份证号码、邮政编码等。
  2. 高效稳定排序需求 在需要保持相等元素原始相对顺序、且对排序效率有较高要求的场景，基数排序的稳定性和高效性使其成为理想选择。
  3. 海量数据处理 对于处理大规模数据集，特别是内存受限但硬盘空间充足的环境，基数排序由于其线性时间复杂度和较低的空间复杂度，能够有效应对大数据排序需求。

  总结来说，基数排序是一种利用元素位值进行排序的非比较型算法，其线性时间复杂度、稳定性以及对特定数据类型的高效处理能力，使其在特定场景下展现出显著优势。理解并恰当运用基数排序，能够有效解决实际问题中涉及大规模数据快速、稳定排序的需求。然而，对于不符合其数据类型要求或内存空间极其受限的场景，选择基数排序时需谨慎评估其适用性。
</p>

<script>
  function radixSort (arr) {
    // 如果arr的长度小于等于1 直接返回arr
    if (arr.length <= 1) return arr

    // 基数
    const base = 10
    // 找出arr中最大值
    const max = Math.max(...arr)
    // 除数 用于分割数值的位数 1 10 100 1000 ...
    let division = 1

    // 除数只要小于arr中最大值就一直循环下去
    while (division <= max) {
      // 创建桶
      const buckets = [...Array(base)].map(() => [])

      // 循环arr
      for (let i = 0, len = arr.length; i < len; i ++) {
        // 计算放入桶的索引
        const index = (arr[i] / division | 0) % base
        // 放入桶中
        buckets[index].push(arr[i])
      }

      // 重置arr
      arr = [].concat(...buckets)

      division *= 10
    }

    // 返回arr
    return arr
  }
  console.log(radixSort([91, 152, 23, 64, 235, 235, 100, 432, 31, 550]))
</script>
</body>
</html>
